package com.lry.basic.algorithm.recursion;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Subsets {

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        if(null==nums||nums.length==0)
            return ans;
        Arrays.sort(nums);
        List<Integer> path = new ArrayList<>();
        boolean[] visited = new boolean[nums.length];
        dfs2(0,nums,visited,ans,path);
        ans.add(new ArrayList<>());
        return ans;
    }

    private void dfs2(int start, int[] nums, boolean[] visited, List<List<Integer>> ans, List<Integer> path) {
        if(!path.isEmpty()){
            ans.add(new ArrayList<>(path));
        }

        for(int i=start;i<nums.length;i++){
            if(!visited[i]){
                if(i>0&&nums[i]==nums[i-1]&&!visited[i-1]){
                    continue;
                }
                visited[i] = true;
                path.add(nums[i]);
                dfs2(i+1,nums,visited,ans,path);
                visited[i] = false;
                path.remove(path.size()-1);
            }
        }
    }

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        if(null==nums||nums.length==0)
            return ans;

        List<Integer> path = new ArrayList<>();
        boolean[] visited = new boolean[nums.length];
        dfs(0,nums,visited,ans,path);
        ans.add(new ArrayList<>());
        return ans;
    }

    private void dfs(int start,int[] nums, boolean[] visited, List<List<Integer>> ans, List<Integer> path) {
        if(!path.isEmpty()){
            ans.add(new ArrayList<>(path));
        }

        for(int i=start;i<nums.length;i++){
            if(!visited[i]){
                visited[i] = true;
                path.add(nums[i]);
                dfs(i+1,nums,visited,ans,path);
                visited[i] = false;
                path.remove(path.size()-1);
            }
        }
    }

    public  static int[][] findContinuousSequence(int target) {
        int start = 1 , end = 1;
        int sum = 0;
        List<int[]> ans = new ArrayList();

        while(start<=target/2){
            if(sum==target){
                int[] num = new int[end-start];
                for(int i=0;i<end-start;i++){
                    num[i] = start+i;
                }
                ans.add(num);
                sum -= start;
                start++;
            }else if(sum>target){
                sum -= start;
                start++;
            }else if(sum<target){
                sum+=end;
                end++;
            }
        }
        return ans.toArray(new int[0][]);
    }

    public static void main(String[] args) {
//        System.out.println(new Subsets().subsets(new int[]{1,  1}));
//        System.out.println(new Subsets().subsetsWithDup(new int[]{1,  1}));
        System.out.println(findContinuousSequence(9));
    }
}
